19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
分析
这个题一看就得用递归，用递归的方式，找到倒数第 N+1 个节点，进行删除，同时因为链表头节点可能被删除，因此得用虚拟头节点法。大概就是这样的思路。
有没有更高级的办法呢？有！双指针法，这个是真的很难想到。没想到这里也能用到双指针法，
双指针法的思路很简单，首先把一个指针 fast 从头往后移动 n，头节点的位置为 1 的话，这个 fast 所在的位置就是 n,反过来 fast 指针的位置为 1 的话，头节点就是 n，虚拟头节点 slow 就是 n+1,然后我们同步移动 slow 和 fast 这两个指针，那么当 fast 指向链表的最后一个元素的时候，slow 指向的就是倒数第 n+1 个节点，也就是待删除节点的前一个结点。
双指针法的精髓，就是先把快指针移动 n，然后再同时移动快指针和慢指针，知道快指针移动到链表的最后一个元素。非常巧妙
解题
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode(-1,head);
removeNode(dummyNode,n);
return dummyNode.next;
}
public int removeNode(ListNode head,int n) {
if(head.next==null){
return 1;
}else{
int reverseIndex = removeNode(head.next,n)+1;
if(reverseIndex==(n+1)){
head.next = head.next.next;
}
return reverseIndex;
}
}
双指针法的实践，确实很简单，很高级
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode dummyHead = new ListNode(-1,head);
// 先往后移动n个节点，注意这里的条件是 i<n 而不是 i<=n
for(int i=1;i<n;i++){
// 因为题目中说了 n小于等于链表的长度，因此，此时 fast.next 不会为空
fast = fast.next;
}
// 跳出循环的时候，i = n,即假设head的位置是1，此时 fast 的位置是 n，因为题目中说了 n小于等于链表的长度，因此，此时 fast 不会为空
// 而 slow/dummyHead 与 fast 的距离是 n+1
ListNode slow = dummyHead;
// 同时移动快慢指针
// 跳出循环的时候，fast为链表最后的元素，slow为待移除元素的前一个元素
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
// 删除元素
slow.next = slow.next.next;
return dummyHead.next;
}